The present invention relates to architectures for fast information retrieval.
Content addressable memories (CAMs) are devices that are queried using data in contrast to conventional memories that are queried using addresses. CAMs search through their contents to check if the data exists, and if so, provide information associated with the data. Such memories find applications in Internet routers, processor caches, databases, and other situations where fast lookups are required. Most commercial routers employ CAM devices called Ternary-CAMs (TCAMs) which are specialized memory devices that check if a query matches every entry in parallel. TCAMs are more expensive that conventional SRAM or DRAM. TCAMs are built using about 16 transistors per bit—therefore being about two to three times less dense than SRAMs which have about 6 transistors per bit. TCAMs have long “match lines” that incur considerable capacitance, thereby causing their power capacitance to be high and, more importantly, their speed to be relatively slow. TCAMs, however, continue to be an attractive proposition for router manufacturers because current commercial technology lacks a viable technique to use conventional SRAM to efficiently perform the lookup.
There are a variety of known data structures that effectively behave like content addressable memory, each with their own relative advantages and disadvantages. For example, trie-based approaches construct a binary trie for each prefix, where a binary trie is a tree with two kinds of nodes: branch nodes and element nodes. Unfortunately, the scalability and memory usage of trie-based approaches are both functions of the address length, which is disadvantageous when used with longer addresses such as in IPv6. Other data structures such as binary decision diagrams cannot be implemented in hardware in a streamlined fashion since they have inherent dependencies and are not scalable to large memories and address lengths. Field-programmable gate array (FPGA)-based approaches use memory and configurable logic block resources to implement a content addressable memory. While these approaches are good for quick prototyping, they are not good candidates for high-speed processing of large prefixes. Recently, Bloom filters have been proposed for network routers, where Bloom filters are known data structures that support membership queries with a small false positive rate. See Dharmapurikar S, K. P., Taylor, D. E., “Longest Prefix Matching Using Bloom Filters,” in Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, August 2003. Separate Bloom filters and hash tables are maintained for each distinct prefix length, and an incoming query is checked for membership in all Bloom filters. Any Bloom filter that results in a positive membership forwards the input query to the hash table corresponding to that prefix length. The drawback with this approach is that hash tables can result in collisions and, therefore, unpredictable performance. Furthermore, the hash tables are queried sequentially in decreasing order of prefix lengths in order to perform longest prefix matching. Another approach has been to construct a binary search tree with a near-optimal depth for a given number of prefixes, so that the worst case lookup time is bounded and deterministic. See P. Gupta, B. Prabhakar, and S. Boyd, “Near-Optimal Routing Lookups with Bounded Worst Case Performance,” Proc. Infocom, Vol. 3, pp. 1184–92, March 2000. Unfortunately, this scheme relies on probabilities for different prefixes.
There is, accordingly, a need for an alternative design that is faster, less expensive and more scalable than existing content addressable memory designs. There is also a need for a practical content-based information retrieval mechanism that can take advantage of conventional memory such as SRAM or DRAM.